Generally mathematical operations in a computer such as, (i) division of a dividend by a divisor to produce a quotient and (ii) square root of a radicand to produce a root, are slow. Such division and square root operations are slow because they require iteratively generating a series of partial remainders, and quotient or root digits respectively.
Therefore, the speed of the division or square root operation is dependent on the amount of time it takes to complete one iteration and the total number of iterations required. The total number of iterations is dependent on the number of quotient or root mantissa digits required to provide an accurate quotient or root. For example, in floating point division twenty-four mantissa digits are required for single precision and fifty-three mantissa digits are required for double-precision, therefore the time required to generate each of the required quotient digits is critical to the speed of the division operation.
Typically, in each iteration of a square root operation, a root digit and a correction term are computed after examining a current partial remainder. The succeeding or partial remainder for the next iteration is computed by subtracting the correction term from the current partial remainder and scaling the result of the subtraction. In each iteration of a division operation, a quotient digit is computed after comparing a current partial remainder and the divisor. The partial remainder for the next iteration is computed by subtracting a multiple of the divisor from the current partial remainder and scaling the result of the subtraction.
Thus, the computation of the partial remainder for the next iteration for both the square root operation and the division operation requires a subtraction operation. Typically the subtraction is performed through the use of Carry Propagate Adders (xe2x80x9cCPAxe2x80x9d) or Carry Save Adders (xe2x80x9cCSAxe2x80x9d). CPAs are relatively slow because a carry bit must be propagated from the Least Significant Bit (xe2x80x9cLSBxe2x80x9d) CPA to the Most Significant Bit (xe2x80x9cMSBxe2x80x9d) CPA. CSAs are much faster but because they present the partial remainder as separate sum and carry binary numbers which must be added, examination of the partial remainder is slower and more complicated.
The tradeoff between examination speed and subtraction speed (CPA and CSAs) is a long standing issue faced by computer divider and square root designers.
In a computer system, a next partial remainder and an output digit is determined by a decoder coupled to an adder, the adder coupled to a scaler. The decoder computes the root digit and binary correction term dependent on a number of digits of a partial remainder. The partial remainder is stored in signed digit format. The adder generates a signed digit result by subtracting the binary correction term from the signed digit partial remainder. The scaler computes the next partial remainder dependent on the signed digit result from the adder.
The signed digit values are selected from a set of digit values. The adder computes a carry out bit independent of the carry in bit. The scaler computes the next signed digit partial remainder by scaling the current signed digit partial remainder upward.
In a computer system, a mathematical square root operation is performed by a decoder coupled to an adder, the adder coupled to a scaler. The decoder computes the root digit and binary correction term dependent on a number of digits of a partial remainder. The partial remainder is stored in signed digit format. The adder generates a signed digit result by subtracting the binary correction term from the signed digit partial remainder. The scaler computes the next partial remainder dependent on the signed digit result from the adder.
The signed digit values are selected from a set of digit values. The set of digit values may be minus one, zero or one, or minus two, minus one, zero, plus one and plus two or any other set of digit values containing more than two digit values. The adder computes a carry out bit independent of the carry in bit. The output signals in the adder may be initialized to predetermined voltage levels. The scaler computes the next signed digit partial remainder by scaling the current signed digit remainder upward.
In a computer system, a mathematical division operation is performed by a decoder coupled to an adder, the adder coupled to a scaler. The decoder computes the quotient digit and binary correction term dependent on a number of digits of a partial remainder. The partial remainder is stored in signed digit format. The adder generates a signed digit result by subtracting the binary correction term from the signed digit partial remainder. The scaler computes the next partial remainder dependent on the signed digit result from the adder.